package com.dyz.LeetCodeforSwordFingerOffer;

/**
 * @author: daiyizheng
 * @date: 2021/7/8 0:34
 * @description:
 */
public class MaxValue47 {
    /**
     * 解题方法，动态规划
     * 一维
     * [1,3,1]--> dp = [0,0,0] -->dp[0]=1 dp[1]=4, dp[2]=5
     * 二维
     * [[1,3]
     * [1,5]]
     * dp[[0,0,0]
     *    [0,0,0]
     *    [0,0,0]
     *    ]
     *    [[0,0,0]
     *     [0,1,4]
     *     [0,2,9]
     *    ]
     *
     *    动态规划 左边与上边哪个最大
     *    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1]
     */
    public int maxValue(int[][] grid) {
        //二维动态规划
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m+1][n+1];
        for(int i=1;i<=m;i++){
            for (int j=1;j<=n;j++){
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1];
            }
        }
        return dp[m][n];
    }

}
